package leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Cheng Jun
 * Description: 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 * 1 <= nums.length <= 8
 * -10 <= nums[i] <= 10
 * @version 1.0
 * @date 2022/8/2 15:08
 */
public class permuteUnique {

    public static void main(String[] args) {
        permuteUnique(new int[]{1, 1, 2});
        //
    }

    /**
     * 思路：使用 回溯思想，重点是在于去重
     *
     * @param nums
     * @return java.util.List<java.util.List < java.lang.Integer>>
     * @author Cheng Jun
     * @date 2022/8/2 15:28
     */
    private static List<List<Integer>> permuteUnique(int[] nums) {
        // [1,1,2]
        // [1,1,2]
        // [1,1,2]
        Arrays.sort(nums);
        int length = nums.length;
        List<List<Integer>> resList = new ArrayList<>();
        backTrack(nums, new boolean[length], 0, new ArrayList<>(), resList);
        return resList;
    }

    // 对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」
    private static void backTrack(
            int[] nums, boolean[] used, int deep, List<Integer> curList, List<List<Integer>> resList) {
        if (deep == nums.length) {
            resList.add(new ArrayList<>(curList));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 当前元素用过，则跳过
            if (used[i]) {
                continue;
            } else { // 当前元素没有用过
                // 如果不是第一个元素，并且前一个的元素没有用过，并且当前元素和前一个元素相同，则跳过
                if (i != 0 && !used[i - 1] && nums[i - 1] == nums[i]) {
                    continue;
                }
            }
            // 简写如下
            // if(used[i] || (i != 0 && !used[i - 1] && nums[i - 1] == nums[i])) continue;
            used[i] = true;
            curList.add(nums[i]);
            backTrack(nums, used, deep + 1, curList, resList);
            curList.remove(curList.size() - 1);
            used[i] = false;
        }
    }
}
